Field of the Invention
This invention is related to technology for managing storage areas in a storage device and allocating files and memory objects to those storage areas.
Description of Related Art
Up to now, file systems such as, for example, FAT (File Allocation Tables) or NTFS (NT File System) have been used as the method to manage data stored in a storage device like a hard disk and so forth.
FIG. 1A is a drawing describing the region allocation for an external storage device such as a hard disk, used in prior art.
For example, as shown in FIG. 1A, a master boot record 195 and a region management table 195a holding region management data are disposed at the beginning of the memory area in the external storage device 306.
Furthermore, by means of an unshown utility program for a disk allocator or other such means, 4 regions, 1 to 4 (191, 192, 193, 194), are allocated and each are assigned to some file system. FIG. 1A shows an example of region management table 195a that includes the region information 196 for region number 3 with its entries of region number 196a, start position 196b, and region size 196c. Region number 196a holds the region number that identifies the region, and in the example it is number 3. The start position holds information on the starting address of the region, and in the example these contents are omitted. Region size 196c holds the number of allocation units for that region and in this example it is 52.
The disk allocation management for the files in each region is complicated because it depends on the allocation methods unique to the file systems assigned to each region.
For example, a FAT keeps a link list showing the blocks allocated to each file. And a NTFS keeps information on the start position and number of contiguous blocks for the blocks allocated to each file.
To resolve the problem of allocation management for each of these files systems, for example, the art of a buddy system was proposed, as disclosed in patent reference 1 and non-patent reference 1 below. A buddy system partitions the storage area in sizes that are a power of 2 and manages allocation that way. A basic buddy system is employed in the allocation of memory objects in a simple system that does not use a virtual storage method.
FIG. 1B is a drawing describing the allocation principles of the buddy system. FIG. 1B shows an assigned area 490 whose size is 2 to the 3rd power (=8) and a tree configuration 580 associated with that assigned area. Assigned area 490 is, for example, one of the regions 1 to 4 shown in the example in FIG. 1A.
The tree configuration 580 models hierarchically the relations between the areas (in the terminology of patent reference 1 these are “extents”) that are successive partitions in two (halving) of the size of assigned area 490 down to a predetermined allocation unit size.
When the partition level at the level of the allocation unit size is taken to be level 0, as shown in the drawing, the level of the root node is 3, in other words, the power-of-2 size of the assigned area 490. [Saying it differently, the partition level number of a given extent expresses the power-of-2 size of that extent, which in turn expresses the number of allocation units that compose that extent.]
The root node 480 of the tree configuration 580 corresponds to the total area (level 3 extent) of the assigned area 490 before partitioning, and the “8” depicted inside the node corresponds to the size of the corresponding assigned area 490. Also, the numbers in parentheses are level-internal numbers to distinguish extents within the same level.
Node 440 connected to the root node 480 by link 540 and node 441 connected to the root node 480 by link 541 correspond to the area (level 2 extent) of the assigned area 490 partitioned in half. The size of each of those extents is the 4 shown in the drawing.
Below node 440 are node 420 with a size of 2 and connected by link 520, and node 421 with a size of 2 and connected by link 521.
In the same way, below node 441 are node 422 with a size of 2 and connected by link 522, and node 423 with a size of 2 and connected by link 523. These 4 nodes correspond to level 1 extents.
Below node 420 are node 410 with a size of 1 and connected by link 510, and node 411 with a size of 1 and connected by link 511.
In the same way, below node 421 are node 412 with a size of 1 and connected by link 512, and node 413 with a size of 1 and connected by link 513, and below node 422 are node 414 with a size of 1 and connected by link 514, and node 415 with a size of 1 and connected by link 515, and below node 423 are node 416 with a size of 1 and connected by link 516, and node 417 with a size of 1 and connected by link 517. These 8 nodes correspond to level 0 extents.
Each of the nodes other than the root node 480 corresponds to one of the two extents that are ½ of the extent corresponding to its parent node. Thus the sum of the extent sizes at each level is equal to the size of the assigned area 490.
In accordance to the above noted buddy system, when a file of a certain size is to be allocated, it is sufficient to search for and allocate an available extent among the extents whose sizes are equal to that file size or exceed it by power-of-2 difference, and when it is released, it is sufficient to return it to the group of available extents with that size, and thus the allocation and release of files and memory objects and the related area management is simplified.    Patent Document 1: JP 1995-28693 A    Non-Patent Document 1: Taku Yasui, “First Study of the Linux Kernel (Part 5 Kernel Memory Management)” Nikkei Linux Vol. 6 No. 1 (2004-01-08) pp 123-130 (in Japanese)